package datastructure;

import java.util.ArrayList;
import java.util.Random;

/**
 * O(logn) for operation, tested on Poj2828
 * 
 * @author yinzichen
 * 
 * @param <T>
 */
public class InsertSkipList<T> {
	class ListNode {
		T val;
		int dist;
		int idx;
		ListNode down;
		ListNode next;

		public ListNode(T val) {
			this.val = val;
			this.idx = -1;
		}
	}

	static final Random ran = new Random(0);
	static final double prob = 0.5;
	ListNode top;
	ListNode head;
	ListNode rear;
	int height;
	int length;

	public InsertSkipList() {
		head = new ListNode(null);
		rear = new ListNode(null);
		head.next = rear;
		head.dist = 1;
		top = head;
		height = 1;
		length = 0;
	}

	private int randomHeight() {
		int h = 0;
		double hasNext;
		do {
			h++;
			hasNext = ran.nextDouble();
		} while (hasNext < prob);
		return h;
	}

	private ArrayList<ListNode> get(int idx, int k) {
		ArrayList<ListNode> level = new ArrayList<ListNode>();
		ListNode cur = top;
		int j = height;
		int curIdx = -1;
		while (cur != null) {
			cur.idx = curIdx;
			while (cur.next != rear && cur.idx + cur.dist < idx) {
				curIdx += cur.dist;
				cur = cur.next;
				cur.idx = curIdx;
			}
			if (j <= k) {
				level.add(cur);
			}
			j--;
			cur = cur.down;
		}
		return level;
	}

	public void insert(int idx, T val) {
		if (idx > length)
			throw new IllegalArgumentException("index out of boundary, idx: "
					+ idx);
		int h = randomHeight();
		while (height < h) {
			ListNode newHead = new ListNode(null);
			newHead.next = rear;
			newHead.down = top;
			newHead.dist = length + 1;
			top = newHead;
			height++;
		}
		ArrayList<ListNode> level = get(idx, height);
		ListNode down = null;
		for (int i = 0; i < height - h; ++i) {
			level.get(i).dist++;
		}
		for (int i = height - 1; i >= height - h; --i) {
			ListNode newNode = new ListNode(val);
			newNode.next = level.get(i).next;
			newNode.down = down;
			newNode.dist = level.get(i).idx + level.get(i).dist + 1 - idx;
			level.get(i).dist = idx - level.get(i).idx;
			level.get(i).next = newNode;
			down = newNode;
		}
		length++;
	}

	public void debug() {
		ListNode curTop = top;
		while (curTop != null) {
			ListNode cur = curTop;
			while (cur != null) {
				System.out.print(cur.dist + " ");
				cur = cur.next;
			}
			System.out.println();
			curTop = curTop.down;
		}
		System.out.println();
	}

	public T get(int idx) {
		if (idx >= length)
			throw new IllegalArgumentException("index out of boundary, idx: "
					+ idx);
		ArrayList<ListNode> level = get(idx, 1);
		ListNode res = level.get(0).next;
		return res.val;
	}

	public T delete(int idx) {
		if (idx >= length)
			throw new IllegalArgumentException("index out of boundary, idx: "
					+ idx);
		ArrayList<ListNode> level = get(idx, height);
		ListNode res = level.get(level.size() - 1).next;

		for (int i = level.size() - 1; i >= 0; --i) {
			if (level.get(i).idx + level.get(i).dist == idx) {
				level.get(i).dist += level.get(i).next.dist;
				level.get(i).next = level.get(i).next.next;
			}
			level.get(i).dist--;
		}
		while (top.down != null && top.next == rear) {
			top = top.down;
			height--;
		}
		length--;
		return res.val;
	}
}
